package month202011;

import org.omg.CORBA.INTERNAL;

import java.util.*;

/**
 * LeetCode 349.两个数组的交集    https://leetcode-cn.com/problems/intersection-of-two-arrays/
 */
public class LeetCode_349_intersection_of_two_arrays {

    public static void main(String[] args) {
        LeetCode_349_intersection_of_two_arrays twoArrays = new LeetCode_349_intersection_of_two_arrays();
//        int[] num1 = new int[]{1,2,2,1};
//        int[] num2 = new int[]{2,2};
        int[] num1 = new int[]{4,9,5};
        int[] num2 = new int[]{94,9,8,4};
        int[] ints = twoArrays.intersection(num1, num2);
        for (int anInt : ints) {
            System.out.print(anInt + " , ");
        }
    }


    /**
     *  时间复杂度：O(N+M+K)
     *      N：第一个数组的长度
     *      M：第二个数组的长度
     *      K：交集数组的长度
     *  空间复杂度：O(N+K)
     *      N：第一个数组的长度
     *      K：交集数组的长度
     * Method 1:
     * 解题思路： 借助 HashMap 来进行实现
     * 1、循环第一个数组，把 数组 值当作 key 存储 HashMap 当中，并把 value 设置为 1
     * 2、循环第二个数组，再 HashMap 中根据数组值 当作 Key 进行查找，，
     * 2.1.能找到并把 value 设置为 2
     * 2.2 找不到 忽略
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            map.put(i, 1);
        }
        List<Integer> list = new ArrayList<>();
        for (int i2 : nums2) {
            if (map.containsKey(i2) && map.get(i2).equals(1)) {
                map.put(i2, 2);
                list.add(i2);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
